/*
 * @Author: Tendo 
 * @Date: 2021-10-22 12:11:39 
 * @Last Modified by:   Tendo 
 * @Last Modified time: 2021-10-22 12:11:39 
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
    // 不使用额外空间，使用中序遍历,设置出现最大次数初始值为1
    let count = 0, maxCount = 1;
    let pre = root, res = [];
    // 1.确定递归函数及函数参数
    const travelTree = function (cur) {
        // 2. 确定递归终止条件
        if (cur === null) { // 第一个节点
            return; // 频率就为maxCount 1
        }
        travelTree(cur.left);
        // 3. 单层递归逻辑
        if (pre.val === cur.val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点
        if (count === maxCount) { // 如果count等于maxCount（最大频率），把这个元素加入结果集中
            res.push(cur.val);
        }
        if (count > maxCount) { // 频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为res数组），因为结果集之前的元素都失效了。
            res = [];
            maxCount = count;
            res.push(cur.val);
        }
        travelTree(cur.right);
    }
    travelTree(root);
    return res;
};